﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Infraestruturex.Automata.SPA;
using Infraestruturex.Automata;

namespace Compilex.Automata
{
    public class DFA : IAutomaton<DFAState>
    {
        public DFAState StartState { get; set; }

        public IBasicTokenProvider TokenProvider { get; set; }

        public DFA()
        {
            TokenProvider = new SequentialCharsTokenProvider();
        }

        public DFA(DFAState startState)
        {
            this.StartState = startState;
        }

        /// <summary>
        /// Verifica se uma cadeia de entrada é aceita por este autômato.
        /// </summary>
        /// <param name="input">A cadeia de entrada. Se for null ou "", é considerada a
        /// cadeia vazia.</param>
        /// <returns>true caso a cadeia seja aceita, false caso contrário</returns>
        public bool Accepts(String input)
        {
            bool useless;
            return Accepts(input, out useless);
        }

        /// <summary>
        /// Verifica se uma cadeia é aceita por este autômato. Se não for,
        /// informa se existe uma cadeia que, concatenada a esta, resultaria
        /// em uma cadeia reconhecida pelo autômato.
        /// </summary>
        /// <param name="input">A cadeia de entrada. Se for null ou "", é considerada
        /// a cadeia vazia.</param>
        /// <param name="isRecoverable">Se a cadeia não for aceita, indica se é
        /// possível concatenar outra cadeia de modo que este autômato passaria a reconhecer
        /// a concatenação. Valor indefinido se a cadeia for aceita.</param>
        /// <returns>true caso a cadeia seja aceita, false caso contrário</returns>
        public bool Accepts(String input, out bool isRecoverable)
        {
            DFAState currentState = StartState;
            TokenProvider.Input = input;
            if (input != null)
            {
                while (TokenProvider.HasMoreTokens() && currentState != null)
                {
                    currentState = currentState.TryGetDestinationState(TokenProvider.PeekNextTokenClass());
                    TokenProvider.ConsumeNextToken();
                }
            }
            if (currentState == null)
            {
                isRecoverable = false;
                return false;
            }
            else
            {
                isRecoverable = true;
                return currentState.IsAcceptState;
            }
        }

        public DFAState[] GetStates()
        {
            HashSet<DFAState> states = new HashSet<DFAState>();
            states.Add(this.StartState);
            int lastStateCount;
            do
            {
                lastStateCount = states.Count;
                HashSet<DFAState> newStates = new HashSet<DFAState>();
                foreach (DFAState state in states)
                {
                    for (int i = 0; i < state.Transitions.Count; i++)
                    {
                        newStates.Add(state.Transitions[i].Destination);
                    }
                }
                states.UnionWith(newStates);
            } while (states.Count > lastStateCount);
            return states.ToArray();
        }
    }
}
